package com.cb2.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/delete-nodes-from-linked-list-present-in-array'>从链表中移除在数组中存在的节点(Delete Nodes From Linked List Present in Array)</a>
 * <p>给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入： nums = [1,2,3], head = [1,2,3,4,5]
 *      输出： [4,5]
 *      解释：移除数值为 1, 2 和 3 的节点。
 *
 *  示例 2：
 *      输入： nums = [1], head = [1,2,1,2,1,2]
 *      输出： [2,2,2]
 *      解释：
 *          移除数值为 1 的节点。
 *
 *  示例 3：
 *      输入： nums = [5], head = [1,2,3,4]
 *      输出： [1,2,3,4]
 *      解释：
 *          链表中不存在值为 5 的节点。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 10^5</li>
 *     <li>1 <= nums[i] <= 10^5</li>
 *     <li>nums 中的所有元素都是唯一的。</li>
 *     <li>链表中的节点数在 [1, 10^5] 的范围内。</li>
 *     <li>1 <= Node.val <= 10^5</li>
 *     <li>输入保证链表中至少有一个值没有在 nums 中出现过。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/9 16:54
 */
public class LC3217DeleteNodesFromLinkedListPresentInArray_M {
    static class Solution {
        public ListNode modifiedList(int[] nums, ListNode head) {
            boolean[] helper = new boolean[100001];
            for (int num : nums) {
                helper[num] = true;
            }

            ListNode dummyHead = new ListNode(-1, head);
            ListNode currNode = dummyHead;
            while (currNode.next != null) {
                if (helper[currNode.next.val]) {
                    currNode.next = currNode.next.next;
                } else {
                    currNode = currNode.next;
                }
            }
            return dummyHead.next;
        }

        public ListNode modifiedList2(int[] nums, ListNode head) {
            Set<Integer> helper = new HashSet<>();
            for (int num : nums) {
                helper.add(num);
            }
            ListNode dummyHead = new ListNode(-1, head);
            ListNode currNode = dummyHead;
            while (currNode.next != null) {
                if (helper.contains(currNode.next.val)) {
                    currNode.next = currNode.next.next;
                } else {
                    currNode = currNode.next;
                }
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.modifiedList(new int[]{1, 2, 3}, Generator.create(1, 2, 3, 4, 5)));
        Printer.printListNode(solution.modifiedList(new int[]{1}, Generator.create(1, 2, 1, 2, 1, 2)));
        Printer.printListNode(solution.modifiedList(new int[]{5}, Generator.create(1, 2, 3, 4)));
    }
}
